This application makes reference to, incorporates the same herein, and claims all benefits accruing under 35 U.S.C. xc2xa7119 from an application entitled A LARGE-SCALED ATM SWITCH WITH FAULT TOLERANT SCHEME AND A SELF-ROUTING METHOD IN A 2Nxc3x97N MULTIPLEXING SWITCH earlier filed in the Korean Industrial Property Office on Jun. 30, 1997, and there duly assigned Serial No. 29587/1997 a copy of which is annexed hereto.
1. Technical Field
The present invention relates to a large-scale fault tolerant asynchronous transfer mode (ATM) switch and a method for implementing a large-scale asynchronous transfer mode (ATM) switch.
2. Related Art
In general, packet-switching technologies are used to relay data traffic via an address contained within a packet. Asynchronous transfer mode (ATM) is one of a class of such packet-switching technologies. Asynchronous transfer mode (ATM) is a telecommunications technique defined by American National Standards Institute (ANSI) and International Telegraph and Telephone Consultative Committee (CCITT).
American National Standards Institute (ANSI) is a nonprofit organization formed in 1918 to coordinate private sector standards development in the United States. The International Telegraph and Telephone Consultative Committee (CCITT) is an international committee established to promote standards for the development of telephone, telegraph systems, and data networks and to create the environment for interworking between the networks of the different countries of the world.
There are different types of asynchronous transfer mode (ATM) switches. The term xe2x80x9cswitch fabricxe2x80x9d refers to the method of data being switched from one node to another within a network. The term xe2x80x9ccellxe2x80x9d refers to a fixed-length unit of data traveling through the switch fabric. Cell switching breaks up data streams into small units that are independently routed through the switch. The routing occurs mostly in hardware through the switching fabric. The combination of cell switching and scaleable switching fabrics are key components of asynchronous transfer mode (ATM).
In the area of asynchronous transfer mode (ATM) data transfer, consider a conventional large-scaled Nxc3x97N switch and a method for implementing a large-scaled Nxc3x97N switch using a 2nxc3x97n multiplexing switch architecture and nxc3x97n output switch. Any type of switch is allowed for the nxc3x97n output switch, but 2nxc3x97n multiplexing switch is made up of output buffering type switches. The multiplexing switch selects just the cells to be transmitted to n output ports, considering the routing tag according to the position of each switch among 2n inputs and transmits the cells as output.
For implementing a large-scale Nxc3x97N switch, 1+log2(N/n) stages are required and each stage needs (N/n) switches. The stages from the first stage to log2(N/n) stage consist of a plurality of 2nxc3x97n multiplexing switches. The last stage consists of a plurality of nxc3x97n output switches. Therefore, (N/n)xc3x97log2(N/n) 2nxc3x97n multiplexing switches and (N/n) nxc3x97n output switches are required to implement a large-scaled Nxc3x97N switch.
As a result of simulation for implementing the conventional large-scale Nxc3x97N switch as mentioned above, it is known that on the average, the buffer within the 2nxc3x97n multiplexing switch that is positioned closest to the nxc3x97n output switch, has the lost cells. In other words, the 2nxc3x97n multiplexing switch at s(log2(N/n),k) has the lost cells. The earlier a stage is, the fewer cells the buffer has. So, it results in that the probability of occurrence of cell loss in the 2nxc3x97n multiplexing switch at the last stage becomes higher, but on the other hand the cell loss ratio at earlier stages becomes considerably lower.
In the 2nxc3x97n multiplexing switch, the cells on the equal conditions are outputted to the n output ports in view of each switch. However there is a problem in that if one of the n output ports had some problems, the cell loss would occur continuously.
A variety of ATM switches and related devices currently exist, as disclosed in U.S. Pat. No. 5,274,642 to Widjaja et al. entitled Output Buffered Packet Switch With A Flexible Buffer Management Scheme, U.S. Pat. No. 5,367,520 to Cordell entitled Method And System For Routing Cells In An ATM Switch, U.S. Pat. No. 5,305,319 to Sowell entitled FIFO For Coupling Asynchronous Channels, U.S. Pat. No. 5,414,703 to Sakaue et al. entitled Asynchronous Cell Switch, U.S. Pat. No. 5,467,347 to Petersen entitled Controlled Access ATM Switch, U.S. Pat. No. 5,493,566 to Ljungberg et al. entitled Flow Control System For Packet Switches, U.S. Pat. No. 5,557,621 to Nakano et al. entitled ATM Switch And Control Method Thereof, U.S. Pat. No. 5,166,926 to Cisneros et al. entitled Packet Address Look-Ahead Technique For Use In Implementing A High Speed Packet Switch, and U.S. Pat. No. 5,130,984 to Cisneros entitled Large Fault Tolerant Packet Switch Particularly Suited For Asynchronous Transfer Mode (ATM) Communication.
Even though a variety of ATM switches and related devices currently exist, I believe that there is a need for an enhanced ATM switch and a self-routing method in order to solve the aforementioned problem.
For solving the above problems, the present invention is intended to provide a large-scale fault tolerant asynchronous transfer mode (ATM) switch to considerably reduce the cell loss probability and a self-routing method in a 2nxc3x97n multiplexing switch to transmit cells more quickly.
A 2nxc3x97n multiplexing switch for a large-scaled fault tolerant ATM switch includes:
2n valid (VD) extracting part which generates a valid (VD) signal and is used to select a cell among the 2n cells inputted every cell period according to the routing tag and to store said cell to a first in first out (FIFO) buffer;
FIFO selecting part which selects the FIFO buffer for each cell selected by using the valid (VD) signal to be stored and transmits the cell to the corresponding FIFO buffer;
2n shared FIFO buffers storing the 2n cells transmitted through the FIFO selecting part;
outputting part transmitting the cells stored in the shared FIFO buffers to the output ports;
cell counting part counting the number of cells stored in the shared FIFO buffers by using the information transmitted from the FIFO selecting part and outputting part;
back-pressure signal generating part which generates the back-pressure signals by using the information from the cell counting part; and
fault detector monitoring the faults of input ports by inputting the 2n valid (VD) signals from the valid (VD) extracting part.
According to one embodiment of a 2nxc3x97n multiplexing switch for a large-scaled fault tolerant ATM switch, it is preferable that the FIFO selecting part further comprises:
FIFO address extracting part generating the address of the FIFO where the inputted cell is to be stored; and
Banyan routing network transmitting the cell to the shared FIFO buffers by using the data generated in the FIFO address extracting part.
According to one embodiment of a 2nxc3x97n multiplexing switch for a large-scaled fault tolerant ATM switch, it is preferable that the FIFO address extracting part further comprises:
2n adders such that one of 2n valid (VD) signals is inputted in an adder and the result of the operation is outputted to the just next stage of the adder; and
2n buffers inputting the output of the adder of the present stage among the 2n adders.
According to one embodiment of a 2nxc3x97n multiplexing switch for a large-scaled fault tolerant ATM switch, it is preferable that the outputting part further comprises:
read FIFO address (RFA) generator generating n read FIFO address (RFA) signals for selecting the FIFO number to be read;
FIFO read enable (FRE) generator generating 2n FIFO read enable (FRE) signals by using the read FIFO address (RFA) signal; and
output-cell multiplexing part transmitting n cells to the output ports among 2n cells read from the shared FIFO buffering part by using the read FIFO address (RFA) signal.
According to one embodiment of a 2nxc3x97n multiplexing switch for a large-scaled fault tolerant ATM switch, it is preferable that the read FIFO address (RFA) generator further comprises:
shift register inputting n fault detection indicators (FDI) sequentially;
n AND-gates which inputs one of n Fault Detection Indicators from the shift register, a signal determined by the cell count (CCNT) from the cell counting part and back-pressure indicator (BPI) respectively;
register inputting the output of each AND-gate simultaneously;
n adders such that the AEN of the register is inputted in an adder and the result of the operation is outputted to the just next stage of the adder; and
n buffers inputting the output of the adder of the present stage among the n adders.
According to one embodiment of a 2nxc3x97n multiplexing switch for a large-scaled fault tolerant ATM switch, it is preferable that the FIFO read enable (FRE) generator generates 2n FRE (FIFO read enable) signals by using (4n+1) comparators, 8n AND-gates and (4n+1) OR-gates.
According to one embodiment of a 2nxc3x97n multiplexing switch for a large-scaled fault tolerant ATM switch, it is preferable that the fault detector comprises two fault signal generators including (2n+1) comparators, 4n AND-gates, (2n+1) OR-gates and shift register and generates the fault signal for each port of input stages.
According to one embodiment of a 2nxc3x97n multiplexing switch for a large-scaled fault tolerant ATM switch, it is preferable that the output cell multiplexing part comprises n 2nxc3x971 multiplexers.
According to one embodiment of a 2nxc3x97n multiplexing switch for a large-scaled fault tolerant ATM switch, it is preferable that the cell counter consists of two subtractors and a counter.
According to one embodiment of a 2nxc3x97n multiplexing switch for a large-scaled fault tolerant ATM switch, it is preferable that the back-pressure signal generating part comprises:
two AND-gates;
two comparators inputting the output of the AND-gates respectively;
OR-gate adding the outputs of the two comparators logically; and
buffer temporally storing the output of the OR gate.
A self-routing method in a 2nxc3x97n multiplexing switch for a large-scaled fault tolerant ATM switch includes the steps of:
searching for the fault of input ports;
informing the result of the search to the switch of the front stage;
receiving the result of fault lines from the rear stage and preventing the cell from being transmitted to the output port corresponding to the result of fault lines;
back-pressure signaling that informs the status if the number of cells stored in the buffer within the switch is more than the specific value; and
stopping transmitting cells for the moment if the back-pressure signal is received.
According to one embodiment of a self-routing method in a 2nxc3x97n multiplexing switch for a large-scaled fault tolerant ATM switch, it is preferable that when it is provided that A indicates the stage of each switch and k indicates the kth position at each stage of nxc3x97n output switch and it is provided that j=└((kxe2x88x921)n2Z)/N┘, where the function └X┘ means the largest integer among the integers less than or equal to X, and Z=((log2(N/n))xe2x88x92A+1), the method includes the steps of:
deciding the value of s(A,k), the switch group which a specific switch belongs to, from the values A, k of the specific switch;
defining switch group, sg(A,j) and initializing the value of routing tag, i;
deciding whether it is satisfied with the condition of ixe2x89xa6[N/n];
deciding whether it is satisfied with the condition of i greater than =[((jN)/(n2Z))+1];
deciding whether it is satisfied with the condition of ixe2x89xa6[((j+1)N)/n2Z];
deciding whether it is satisfied with the condition of f(i)=0; and
performing cell-transmission.
According to one embodiment of a self-routing method in a 2nxc3x97n multiplexing switch for a large-scaled fault tolerant ATM switch, it is preferable that the cell-transmission is not performed if it is not satisfied with the condition of ixe2x89xa6[N/n].
According to one embodiment of a self-routing method in a 2nxc3x97n multiplexing switch for a large-scaled fault tolerant ATM switch, it is preferable that if it is not satisfied with the conditions, i greater than =[((jN)/(n2Z))+1], ixe2x89xa6[((j+1)N)/n2Z], f(i)=0, then the value of the routing tag, i is incremented by 1 and it is decided whether it is satisfied with the condition of ixe2x89xa6[N/n].
The present invention is more specifically described in the following paragraphs by reference to the drawings attached only by way of example.